package leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 * <p>
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * https://leetcode-cn.com/problems/pascals-triangle-ii/
 * @version 1.0
 * @date 2021/12/29 15:43
 */
public class getRow {

    // 输入: rowIndex = 3
    // 输出: [1,3,3,1]
    //         1
    //       1   1
    //     1   2   1
    //   1   3    3   1
    // 1   4    6   4   1
    public List<Integer> getRow(int rowIndex) {
        List<Integer> originalList = new ArrayList<>();
        originalList.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            // 初始化时，设置数组大小，避免扩容
            List<Integer> curList = new ArrayList<>(originalList.size() + 1);
            // 第一个元素为 1
            curList.add(1);
            for (int j = 0; j < originalList.size() - 1; j++) {
                // 设置下一行的中间元素
                curList.add(originalList.get(j) + originalList.get(j + 1));
            }
            // 最后一个元素为 1
            curList.add(1);
            originalList = curList;
        }
        return originalList;
    }

}
